#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


class Solution {
public:
    vector<int> countBits(int num) {
        if(num==0){
            return {0};
        }
        if(num==1){
            return {0,1};
        }
        //使用dp
        vector<int> dp(num+1,0);
        //dp初始化
        for(int i =0;i<=num;++i){
            if(i==0){
                dp[i] = 0;
            }
            else if(i==1){
                dp[i] = 1;
            }
            else{
                //分奇偶处理
                if(i%2==0){
                    dp[i] = dp[i/2];
                }
                else{
                    dp[i] = dp[i-1]+1;
                }
            }
        }
        return dp;
    }
};


int main(){
    Solution S;
    vector<int> result = S.countBits(9);
    return 0;
}